本博客从入门级到 Ynoi 全覆盖 ~~（确信）~~，欢迎评论、点赞、转发！（日常营销号）

如果以下内容有错误，欢迎指出！转载全文或部分前请先联系作者。

同步发布于洛谷博客。

0x1 分块&块状数组

分块，顾名思义，就是将原数列分成若干块（一般取 $\sqrt{n}$ 左右，可以动态也可以取常数），进行的快速统计的方法。块状数组类似于线段树，维护区间的信息。

例题 1：P3372 【模板】线段树 1

（好好写线段树它不香吗）

由于块状数组的复杂度不正确，不保证此做法能在任意时刻通过此题，仅以此题为例讲解思路。

我们将原数列分成块长为 $320$ 的若干个块，对于每一块，我们记录一个块内的和和一个懒标记。修改时，若左右端点在同一块，直接暴力修改原数组和分块；若不在同一块，暴力修改左右零散块，中间整块修改块内的和以及懒标记。查询时类似，记得懒标记下放。

时间复杂度为 $O(n\sqrt{n})$ 。

容易写出代码：

//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 1e5+5, SIZE = 320, K = 320;

ll n, m, a[N], s[K], tag[K], L[K], R[K], tot;
#define whichBlock(x) (\
	(x-1)/SIZE+1\
)
void initBlock() {
	tot = whichBlock(n);
	for(ll i=1;i<=tot;i++) {
		L[i] = R[i-1] + 1;
		R[i] = i * SIZE;
		for(ll j=L[i];j<=min(R[i],n);j++) s[i] += a[j];
	}
	R[tot] = n;
}
void pushdown(ll u) {
	ll X = whichBlock(u);
	if(!tag[X]) return;
	for(ll i=L[X];i<=R[X];i++) a[i] += tag[X];
	tag[X] = 0;
}
void modify(ll l, ll r, ll k) {
	ll X = whichBlock(l), Y = whichBlock(r);
	if(X == Y) for(ll i=l;i<=r;i++) a[i] += k, s[X] += k;
	else {
		for(ll i=l;i<=R[X];i++) a[i] += k, s[X] += k;
		for(ll i=X+1;i<Y;i++) tag[i] += k, s[i] += (R[i] - L[i] + 1) * k;
		for(ll i=L[Y];i<=r;i++) a[i] += k, s[Y] += k;
	}
}
ll query(ll l, ll r) {
	ll X = whichBlock(l), Y = whichBlock(r), ans = 0;
	if(X == Y) {
		pushdown(l);
		for(ll i=l;i<=r;i++) ans += a[i];
	}
	else {
		pushdown(l);
		for(ll i=l;i<=R[X];i++) ans += a[i];
		for(ll i=X+1;i<Y;i++) ans += s[i];
		pushdown(r);
		for(ll i=L[Y];i<=r;i++) ans += a[i];
	}
	return ans;
}

int main() {
	scanf("%lld%lld", &n, &m);
	for(ll i=1;i<=n;i++) scanf("%lld", &a[i]);
	initBlock();
	while(m--) {
		ll op, l, r, x;
		scanf("%lld%lld%lld", &op, &l, &r);
		if(op == 1) {
			scanf("%lld", &x);
			modify(l, r, x);
		}
		else printf("%lld\n", query(l, r));
	}
	return 0;
}

【完结撒花！】

其实分块大概就是这样，基础部分练习完了，我们来看几道习题。

部分习题有题解，不做额外讲解；其他的大概提思路。

习题 1：P5309 [Ynoi2011]初始化 | 题解

习题 2：P5356 [Ynoi2017]由乃打扑克 | 题解

0x2 莫队

例题 1：P1972 [SDOI2009]HH的项链

不过这题好像把莫队卡了，那就好好用树状数组吧。

没关系，我们有双倍经验。

例题 1.5：SP3267 DQUERY - D-query

统计区间内颜色个数，怎么办呢？

我们考虑暴力。每次暴力统计一遍太费时间了，我们搞两个指针，表示当前统计到的区间，然后在用一个数组存每个颜色在区间内有多少个，一个变量存区间内有多少颜色即可。统计到下一个区间，我们移动这两个指针（实时更新数组内的值），通过上面提到的数组来更新变量（颜色）的值。

但是这样很容易被卡：询问 $[1,1],[n,n],[2,2],[n-1,n-1]\cdots$ 效率明显低下。怎么办呢？离线做法，先对询问进行排序！

排序的伪代码：

结构体 Query {int l, r, id;}
比较(Query a, Query b):
    如果 a.l 与 b.l 在同一块中:
        比较 a.r 与 b.r 并返回
    否则：
        比较 a.l 与 b.l 并返回

在排序后，这个算法的效率是更高的，可以算出复杂度为 $O(n\sqrt{n})$ 。

（写作时间紧张，复杂度证明先咕了，改天再加）

例题 2：P2709 小B的询问

统计区间内不同数的个数的平方和，与上面类似，采用莫队。

//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
using namespace std;
const int N = 5e4+5, SIZE = 250;

int n, m, k, a[N], tot, s[N], ans[N];
#define whichBlock(x) (\
	(x-1)/SIZE+1\
)
struct Node {
	int l, r, id;
	friend bool operator < (const Node &a, const Node &b) { // 排序方法
		int x = whichBlock(a.l), y = whichBlock(b.l);
		if(x == y) return a.r < b.r;
		return x < y;
	}
}q[N];

void modify(int x, int y) { // 莫队指针移动更新数据
	int z = a[x];
	tot -= s[z] * s[z];
	s[z] += y;
	tot += s[z] * s[z];
}

int main() {
	scanf("%d%d%d", &n, &m, &k);
	for(int i=1;i<=n;i++) scanf("%d", &a[i]);
	for(int i=1;i<=m;i++) {
		scanf("%d%d", &q[i].l, &q[i].r);
		q[i].id = i;
	}
	sort(q+1, q+1+m);
	int l = 1, r = 0;
	for(int i=1;i<=m;i++) {
		while(l < q[i].l) modify(l++, -1); // 移动指针
		while(l > q[i].l) modify(--l, 1);
		while(r < q[i].r) modify(++r, 1);
		while(r > q[i].r) modify(r--, -1);
		ans[q[i].id] = tot;
	}
	for(int i=1;i<=m;i++) printf("%d\n", ans[i]);
	return 0;
}

习题 1：P1494 [国家集训队]小Z的袜子

小Z的妹子袜子这题需要一定的数学推导，和上面那题类似，也需要维护区间平方和。

习题 2：P4688 [Ynoi2016]掉进兔子洞 | 题解

用 bitset 套莫队即可。

完结撒花！

带修莫队和树上莫队因为自己还没做所以先不写了，以后会写新博客更新的~

~~（话说我这么用 Ynoi 当习题会不会被打）~~